package leetcode.Hot100;

import leetcode.TreeNode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author Cheng Jun
 * Description: 给定一个二叉树，找出其最大深度。
 * <p>
 * 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
 * <p>
 * 说明: 叶子节点是指没有子节点的节点。
 * https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/
 * @version 1.0
 * @date 2021/12/3 13:44
 * 二刷
 */
public class maxDepth {

    static int DEPTH = 0;

    public static void main(String[] args) {
        TreeNode a = new TreeNode(3);
        TreeNode b = new TreeNode(2, a, null);
        TreeNode c = new TreeNode(1, b, null);
        System.out.println(maxDepth(c));
        System.out.println(maxDepth1(c));
        System.out.println(maxDepth2(c));
    }

    /**
     * 注意仔细体会 maxDepth 和 maxDepth1 的不同，maxDepth是从上往下 不断累积计数， maxDepth1 是从下往上 不断累积计数
     */
    // 遍历每一条路径，到达叶子节点
   public static int maxDepth(TreeNode root) {
        getDepth(root, 0);
        return DEPTH;
    }

    // 回溯
    static void getDepth(TreeNode node, int nodeDepth) {
        if (node == null) {
            DEPTH = Math.max(DEPTH, nodeDepth);
            return;
        } else {
            nodeDepth += 1;
            getDepth(node.left, nodeDepth);
            getDepth(node.right, nodeDepth);
            nodeDepth--;
        }
    }

    // 深度优先搜索
    // 节点的最大深度等于左右子节点的最大值加 1, ===》 Math.max(l, r) + 1
    public static int maxDepth1(TreeNode root) {
        if (root == null) {
            return 0;
        } else {
            int leftDept = maxDepth1(root.left);
            int rightDept = maxDepth1(root.right);
            return Math.max(leftDept, rightDept) + 1;
        }
    }

    // 广度优先搜索，可以学习一下
    public static int maxDepth2(TreeNode root) {
        if (root == null) {
            return 0;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int ans = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size > 0) {
                TreeNode node = queue.poll();
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
                size--;
            }
            ans++;
        }
        return ans;
    }

}
